package Sort;
/*
* 快速排序
*6.1 算法描述
快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：
快速排序也是利用分治思想。
如果要排序一组数据，我们先选择这组数据中任意一个数据作为分区点pivot，然后遍历这组数据，
*将小于分区点pivot的放到左边，大于分区点pivot的放到右边，将pivot放到中间。然后再分别对左右两部分进行排序。
*
* 快速排序是一种不稳定算法。
* 快速排序是的最好时间复杂度、平均时间复杂度为O(nlogn)
* 但是在极端情况下，如果数组中的数据原来就是有序的 时间复杂度为O(n^2)，也就是最坏时间复杂度。
* */
public class QuickSort {

    public static int[] qsort(int arr[],int start,int end){
        if(start<end){
            int pivot = arr[start];
            int i = start;
            int j = end;
            while (i<j){
                //从后往前找到第一个小于分界值的下标
                while ((i<j)&&(arr[j]>pivot)){
                    j--;
                }
                if(i<j){
                    arr[i++] = arr[j];
                }
                //从前往后找到第一个大于分界值的下标
                while ((i<j)&&(arr[i]<pivot)){
                    i++;
                }
                if(i<j){
                    arr[j--] = arr[i];
                }
            }
            arr[i] = pivot;
            arr = qsort(arr,start,i-1);  //继续排序右边
            arr = qsort(arr,j+1,end);   //继续排序左边
        }
        return arr;
    }

    public static void main(String[] args) {
        int arr[] = new int[]{4,6,7,3,5,4,9,1};
        int len = arr.length-1;
        arr=qsort(arr,0,len);
        for (int i:arr) {
            System.out.print(i+"\t");
        }
    }

}
